package com.yun.algorithmproblem.leetcode;

public class Leetcode28_KMP {
	public static void main(String[] args) {
		Leetcode28_KMP test=new Leetcode28_KMP();
		System.out.println(test.strStr("aaacaaab","aaab"));
	}
    public int strStr(String str1,String str2){
        char[] origin=str1.toCharArray();//原始
        char[] pattern=str2.toCharArray();//模式
        int[] lps=lps(pattern);//最长前后缀数组
        /*
            1.匹配成功,i++,j++,直到j==模式字符串长度
            2.匹配失败
                j!=0 跳过最长前后缀字符,继续匹配
                j==0 则i++
         */
        int i=0,j=0,sub=origin.length- pattern.length;
        while (i-j<=sub){
            if(origin[i]==pattern[j]){
                i++;
                j++;
                if(j== pattern.length){
                    //找到解
                    return i- j;
                }
            }else if(j==0){
                i++;
            }else {
                j=lps[j-1];
            }
        }
        return -1;
    }

    private int[] lps(char[] pattern){
        int[] lps=new int[pattern.length];
        int i=1,j=0;
        while (i< pattern.length){
            if(pattern[i]==pattern[j]){
                lps[i]=j+1;
                i++;
                j++;
            }else if(j==0){
                i++;
            }else {
                j=lps[j-1];

            }
        }
        return lps;
    }

	public int strStr1(String str1,String str2){
		char[] origin=str1.toCharArray();
		char[] pattern=str2.toCharArray();
		int i=0,j=0;
		while (i<=origin.length- pattern.length){
			for (j = 0; j < pattern.length; j++) {
				if(pattern[j]!=origin[i+j]){
					break;
				}
			}
			if(j== pattern.length){
				return i;
			}
			i++;
		}
		return -1;
	}
}
